#include <iostream>
#include <vector>
using namespace std;
// 状态压缩，空间优化
// 1. dp[j]表示放入容量为j的背包能获得的最大价值
// 2. dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
// 3. dp[0] = 0;
// 4. 先遍历物品 还是先遍历容量?
// 容量一定要倒序遍历，如果遍历背包容量放在上一层，那么每个dp[j]就只会放入一个物品

// 遍历容量为何要逆序？保证物品i只被放入一次！

// 为什么二维dp数组历的时候不用倒序呢？因为对于二维dp，dp[i][j]都是通过上一层即dp[i
// - 1][j]计算而来，本层的dp[i][j]并不会被覆盖！
// 5. debug
void test_1_wei_bag_problem() {
  vector<int> weight = {1, 3, 4};
  vector<int> value = {15, 20, 30};
  int bagWeight = 4;

  // 初始化
  vector<int> dp(bagWeight + 1, 0);
  for (int i = 0; i < weight.size(); i++) {         // 遍历物品
    for (int j = bagWeight; j >= weight[i]; j--) {  // 遍历背包容量
      dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
  }
  cout << dp[bagWeight] << endl;
}

// 1. dp[i][j]表示下标0-i的物品中任选 放入容量为j的背包能获得的最大价值
// 2. dp[i][j] = max(dp[i-1][j], dp[i-1][j - weight[i]] + value[i]);
// 3. dp[i][0] = 0;dp[0][j] = ？,j 与 weight[0]关系
// 4. 先遍历物品 还是 先遍历容量
// 都无所谓，都可以；一个新状态由它的左上方和上方推出来；
// 5. debug
void test_2_wei_bag_problem() {
  vector<int> weight = {1, 3, 4};
  vector<int> value = {15, 20, 30};
  int bagweight = 4;

  // 二维数组
  vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));

  // 初始化
  for (int j = weight[0]; j <= bagweight; j++) {
    dp[0][j] = value[0];
  }

  // weight数组的大小 就是物品个数
  for (int i = 1; i < weight.size(); i++) {  // 遍历物品
    for (int j = 0; j <= bagweight; j++) {   // 遍历背包容量
      if (j < weight[i])  // 选不了第i件，没那个能力，知道吧
        dp[i][j] = dp[i - 1][j];
      else  // 选第i件 和 不选第i件，公平pk
        dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
    }
  }

  cout << dp[weight.size() - 1][bagweight] << endl;
}
int main() {
  test_1_wei_bag_problem();
  test_2_wei_bag_problem();
  return 0;
}
